home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_13_09 / pjp / bitset < prev   
Encoding:
Text File  |  1995-07-09  |  8.0 KB  |  245 lines
  1. ------------- Listing 1: The Header <bitset> ---------
  2.  
  3. // bitset standard header
  4. #ifndef _BITSET_
  5. #define _BITSET_
  6. #include <climits>
  7. #include <istream>
  8.         // TEMPLATE CLASS bitset
  9. _STD_BEGIN
  10. template<size_t _N> class bitset {
  11.     typedef unsigned long _T;
  12. public:
  13.     class reference {
  14.     friend class bitset<_N>;
  15.     public:
  16.         reference& operator=(bool _X)
  17.             {_Pbs->set(_Off, _X);
  18.             return (*this); }
  19.         reference& operator=(const reference& _Bs)
  20.             {_Pbs->set(_Off, bool(_Bs));
  21.             return (*this); }
  22.         reference& flip()
  23.             {_Pbs->flip(_Off);
  24.             return (*this); }
  25.         bool operator~() const
  26.             {return (!_Pbs->test(_Off)); }
  27.         operator bool() const
  28.             {return (_Pbs->test(_Off)); }
  29.     private:
  30.         reference(bitset<_N>& _X, size_t _P)
  31.             : _Pbs(&_X), _Off(_P) {}
  32.         bitset<_N> *_Pbs;
  33.         size_t _Off;
  34.         };
  35.     bool at(size_t _P) const
  36.         {if (_N <= _P)
  37.             _Xran();
  38.         return (test(_P)); }
  39.     reference at(size_t _P)
  40.         {if (_N <= _P)
  41.             _Xran();
  42.         return (reference(*this, _P)); }
  43.     const bool operator[](size_t _P) const
  44.         {return (test(_P)); }
  45.     reference operator[](size_t _P)
  46.         {return (reference(*this, _P)); }
  47.     bitset()
  48.         {_Tidy(); }
  49.     bitset(unsigned long _X)
  50.         {_Tidy();
  51.         for (size_t _P = 0; _X != 0 && _P < _N; _X >>= 1, ++_P)
  52.             if (_X & 1)
  53.                 set(_P); }
  54.     explicit bitset(const string& _S, size_t _P = 0,
  55.         size_t _L = (size_t)(-1))
  56.         {if (_S.size() < _P)
  57.             _Xran();
  58.         if (_S.size() - _P < _L)
  59.             _L = _S.size() - _P;
  60.         if (_N < _L)
  61.             _L = _N;
  62.         _Tidy(), _P += _L;
  63.         for (size_t _I = 0; _I < _L; ++_I)
  64.             if (_S[--_P] == '1')
  65.                 set(_I);
  66.             else if (_S[_P] != '0')
  67.                 _Xinv(); }
  68.     bitset<_N>& operator&=(const bitset<_N>& _R)
  69.         {for (int _I = _Nw; 0 <= _I; --_I)
  70.             _A[_I] &= _R._W(_I);
  71.         return (*this); }
  72.     bitset<_N>& operator|=(const bitset<_N>& _R)
  73.         {for (int _I = _Nw; 0 <= _I; --_I)
  74.             _A[_I] |= _R._W(_I);
  75.         return (*this); }
  76.     bitset<_N>& operator^=(const bitset<_N>& _R)
  77.         {for (int _I = _Nw; 0 <= _I; --_I)
  78.             _A[_I] ^= _R._W(_I);
  79.         return (*this); }
  80.     bitset<_N>& operator<<=(size_t _P)
  81.         {if (_P < 0)
  82.             return (*this >>= -_P);
  83.         const int _D = _P / _Nb;
  84.         if (_D != 0)
  85.             for (int _I = _Nw; 0 <= _I; --_I)
  86.                 _A[_I] = _D <= _I ? _A[_I - _D] : 0;
  87.         if ((_P %= _Nb) != 0)
  88.             {for (int _I = _Nw; 0 < _I; --_I)
  89.                 _A[_I] = (_A[_I] << _P)
  90.                     | (_A[_I - 1] >> (_Nb - _P));
  91.             _A[0] <<= _P, _Trim(); }
  92.         return (*this); }
  93.     bitset<_N>& operator>>=(size_t _P)
  94.         {if (_P < 0)
  95.             return (*this <<= -_P);
  96.         const int _D = _P / _Nb;
  97.         if (_D != 0)
  98.             for (int _I = 0; _I <= _Nw; ++_I)
  99.                 _A[_I] = _D <= _Nw - _I ? _A[_I + _D] : 0;
  100.         if ((_P %= _Nb) != 0)
  101.             {for (int _I = 0; _I < _Nw; ++_I)
  102.                 _A[_I] = (_A[_I] >> _P)
  103.                     | (_A[_I + 1] << (_Nb - _P));
  104.             _A[_Nw] >>= _P; }
  105.         return (*this); }
  106.     bitset<_N>& set()
  107.         {_Tidy(~(_T)0);
  108.         return (*this); }
  109.     bitset<_N>& set(size_t _P, bool _X = true)
  110.         {if (_N <= _P)
  111.             _Xran();
  112.         if (_X)
  113.             _A[_P / _Nb] |= (_T)1 << _P % _Nb;
  114.         else
  115.             _A[_P / _Nb] &= ~((_T)1 << _P % _Nb);
  116.         return (*this); }
  117.     bitset<_N>& reset()
  118.         {_Tidy();
  119.         return (*this); }
  120.     bitset<_N>& reset(size_t _P)
  121.         {return (set(_P, 0)); }
  122.     bitset<_N> operator~() const
  123.         {return (bitset<_N>(*this).flip()); }
  124.     bitset<_N>& flip()
  125.         {for (int _I = _Nw; 0 <= _I; --_I)
  126.             _A[_I] = ~_A[_I];
  127.         _Trim();
  128.         return (*this); }
  129.     bitset<_N>& flip(size_t _P)
  130.         {if (_N <= _P)
  131.             _Xran();
  132.         _A[_P / _Nb] ^= (_T)1 << _P % _Nb;
  133.         return (*this); }
  134.     unsigned long to_ulong() const
  135.         {enum {_Assertion = 1 /
  136.             (sizeof (unsigned long) % sizeof (_T) == 0)};
  137.         int _I = _Nw;
  138.         for (; sizeof (unsigned long) / sizeof (_T) <= _I; --_I)
  139.             if (_A[_I] != 0)
  140.                 _Xoflo();
  141.         unsigned long _V = _A[_I];
  142.         for (; 0 <= --_I; )
  143.             _V = _V << _Nb | _A[_I];
  144.         return (_V); }
  145.     string to_string() const
  146.         {string _S;
  147.         _S.reserve(_N);
  148.         for (size_t _P = _N; 0 < _P; )
  149.             _S += test(--_P) ? '1' : '0';
  150.         return (_S); }
  151.     size_t count() const
  152.         {size_t _V = 0;
  153.         for (int _I = _Nw; 0 <= _I; --_I)
  154.             for (_T _X = _A[_I]; _X != 0; _X >>= 4)
  155.                 _V += "\0\1\1\2\1\2\2\3"
  156.                     "\1\2\2\3\2\3\3\4"[_X & 0xF];
  157.         return (_V); }
  158.     size_t size() const
  159.         {return (_N); }
  160.     bool operator==(const bitset<_N>& _R) const
  161.         {for (int _I = _Nw; 0 <= _I; --_I)
  162.             if (_A[_I] != _R._W(_I))
  163.                 return (false);
  164.         return (true); }
  165.     bool operator!=(const bitset<_N>& _R) const
  166.         {return (!(*this == _R)); }
  167.     bool test(size_t _P) const
  168.         {if (_N <= _P)
  169.             _Xran();
  170.         return ((_A[_P / _Nb] & ((_T)1 << _P % _Nb)) != 0); }
  171.     bool any() const
  172.         {for (int _I = _Nw; 0 <= _I; --_I)
  173.             if (_A[_I] != 0)
  174.                 return (true);
  175.         return (false); }
  176.     bool none() const
  177.         {return (!any()); }
  178.     bitset<_N> operator<<(size_t _R) const
  179.         {return (bitset<_N>(*this) <<= _R); }
  180.     bitset<_N> operator>>(size_t _R) const
  181.         {return (bitset<_N>(*this) >>= _R); }
  182.     friend bitset<_N> operator&(const bitset<_N>& _L,
  183.         const bitset<_N>& _R)
  184.         {return (bitset<_N>(_L) &= _R); }
  185.     friend bitset<_N> operator|(const bitset<_N>& _L,
  186.         const bitset<_N>& _R)
  187.         {return (bitset<_N>(_L) |= _R); }
  188.     friend bitset<_N> operator^(const bitset<_N>& _L,
  189.         const bitset<_N>& _R)
  190.         {return (bitset<_N>(_L) ^= _R); }
  191.     friend istream& operator>>(istream& _I, bitset<_N>& _R)
  192.         {ios_base::iostate _St = ios_base::goodbit;
  193.         bool _Chgd = false;
  194.         string _X;
  195.         size_t _M = _N;
  196.         _X.reserve(_M);
  197.         if (_M == (size_t)(-1))
  198.             --_M;
  199.         if (_I.ipfx())
  200.             {_TRY_IO_BEGIN
  201.             int _Ch;
  202.             while (0 < _M)
  203.                 if ((_Ch = _I.rdbuf()->sbumpc()) == EOF)
  204.                     {_St |= ios_base::eofbit;
  205.                     break; }
  206.                 else if (_Ch != '0' && _Ch != '1')
  207.                     {_I.rdbuf()->sputbackc(_Ch);
  208.                     break; }
  209.                 else
  210.                     _X += (char)_Ch, _Chgd = true, --_M;
  211.             _CATCH_IO_(_I); }
  212.         if (!_Chgd)
  213.             _St |= ios_base::failbit;
  214.         _I.isfx();
  215.         if (_St)
  216.             _I.setstate(_St);
  217.         _R = _X;
  218.         return (_I); }
  219.     friend ostream& operator<<(ostream& _O, const bitset<_N>& _R)
  220.         {return (_O << _R.to_string()); }
  221.     _T _W(size_t _I) const
  222.         {return (_A[_I]); }
  223. private:
  224.     enum {_Nb = CHAR_BITS * sizeof (_T),
  225.         _Nw = _N == 0 ? 0 : (_N - 1) / _Nb};
  226.     void _Tidy(_T _X = 0)
  227.         {for (int _I = _Nw; 0 <= _I; --_I)
  228.             _A[_I] = _X;
  229.         if (_X != 0)
  230.             _Trim(); }
  231.     void _Trim()
  232.         {if (_N % _Nb != 0)
  233.             _A[_Nw] &= ((_T)1 << _N % _Nb) - 1; }
  234.     void _Xinv() const
  235.         {invalid_argument("invalid bitset<N> char")._Raise(); }
  236.     void _Xoflo() const
  237.         {overflow_error(
  238.             "bitset<N> conversion overflow")._Raise(); }
  239.     void _Xran() const
  240.         {out_of_range("invalid bitset<N> position")._Raise(); }
  241.     _T _A[_Nw + 1];
  242.     };
  243. _STD_END
  244. #endif /* _BITSET */
  245.